void Swap(int *arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
void AdjustHeap(int *arr, int i, int arrSize)
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largestIndex = i;
    if (left < arrSize && arr[left] > arr[i]) {
        largestIndex = left;
    }
    if (right < arrSize && arr[right] > arr[largestIndex]) {
        largestIndex = right;
    }
    if (i != largestIndex) {
        Swap(arr, i, largestIndex);
        AdjustHeap(arr, largestIndex, arrSize);
    }
}

int findKthLargest(int* nums, int numsSize, int k){
    for (int i = numsSize / 2 - 1; i >= 0; i--) {
        AdjustHeap(nums, i, numsSize);
    }
    int arrSize = numsSize;
    for (int i = 0; i < k - 1; i++) {
        Swap(nums, 0, numsSize - 1 - i);
        arrSize--;
        AdjustHeap(nums, 0, arrSize);
    }
    return nums[0];
}

